本章围绕列表结构的高效实现逐步展开，包括其ADT接口规范以及对应的算法。此外还针对有序列表，系统地介绍排序等经典算法，并就其性能做一分析和对比。
上一章介绍的向量结构中，各数据项的物理存放位置与逻辑次序完全对应，故可通过秩(Rank)访问对应的元素，此即所谓”循秩访问”(call-by-rank)。本章介绍的列表，与向量同属序列结构的范畴，其中的元素也构成一个线性逻辑次序；但与向量极为不同的是，元素的物理地址可以任意。
为保证对列表元素访问的可行性，逻辑上互为前驱和后继的元素之间，应维护某种索引关系。这种索引关系，可抽象地理解为被索引元素的位置(position)，故列表元素是“循位置访问”(call-by-position)的；也可形象地理解为通往被索引元素的链接(link)，故也称”循链接访问“(call-by-link)。
注意，向量中的秩同时对应于逻辑和物理次序，而位置仅对应于逻辑次序。
3.1 从向量到列表
3.1.1 从静态到动态
数据结构支持的操作分为静态和动态两种：前者仅从中获取信息，后者则会修改数据结构的局部甚至整体。以第二章基于数组实现的向量结构为例，其size()和get()等静态操作均可在常数时间内完成，而insert()和remove()等动态操作却都可能需要线性时间。其原因在于”各元素物理地址连续”的约定——此即所谓的“静态存储”策略。
在静态策略下，静态操作的效率可达到极致，但就动态操作而言，局部的修改可能引起大范围甚至整个数据结构的修改，比如在静态策略下在$O(1)$时间内由秩确定向量元素的物理地址，但插入某个元素可能需要移动$O(n)$个后继元素。
列表(list)结构虽然也要求各元素在逻辑上具有线性次序，但对其物理地址未作任何限制——此即所谓“动态存储”策略。具体地，在其生命期内，此类数据结构将随着内部数据的需要，相应地分配或回收局部的数据空间。如此，元素之间的逻辑关系得以延续，却不必与其物理次序相关。作为补偿，此类结构将通过指针或引用等机制，来确定各元素的实际物理地址。采用动态存储策略，可以大大降低动态操作的成本。
3.1.2 由秩到位置
改用动态存储策略之后，在提高动态操作效率的同时，却又不得不舍弃原静态存储策略中循秩访问的方式，从而造成静态操作性能的下降。
以采用动态存储策略的线性结构(链表)为例。每个数据元素虽然仍有秩，但为了访问秩为r的元素，只能顺着相邻元素之间的指针，从某一端出发逐个扫描各元素，经过r步迭代后才能确定该元素的物理存储位置。原先只需$O(1)$时间的静态操作，此时的复杂度也将线性正比于被访问元素的秩，在最坏情况下等于元素总数n；即便在各元素被访问效率相等的情况下，平均而言也需要$O(n)$时间。
对数据结构的访问方式，应与其存储策略相一致。此时应更多地习惯于通过位置，来指代并访问动态存储结构中的数据元素。列表中的位置与向量中秩的地位与功能类似，也是指代各数据元素的一个标识性指标，借助它可以便捷地(比如在常熟时间内)得到元素的物理存储地址。各元素的位置，通常可表示和实现为联接在于元素之间的指针或引用。
3.1.3 列表
与向量一样，列表也是由具有线性逻辑次序的一组元素构成的集合:
$L = { a_0, a_1, … , a_{n-1} } $
列表是链表结构的一般化推广，其中的元素称作节点(node)，分别由特定的位置或链接指代。与向量一样，在元素之间，也可定义前驱、直接前驱、以及后继、直接后继等关系；相对于任意元素，也有定义对应的前缀、后缀等子集。没有前驱/后继的节点称作首(first/front)/末(last/rear)节点。
3.2 接口
列表节点(listnode)是列表的基本组成单位，列表节点应保存对应的数据项，还应记录其前驱和后继的位置。
3.2.1 列表节点
ADT接口
作为一种抽象数据类型，列表节点对象应支持以下操作接口。
| 操作接口 | 功能 |
|---|---|
data() |
当前节点所存数据对象 |
pred() |
当前节点前驱节点的位置 |
succ() |
当前节点后继节点的位置 |
insertAsPred() |
插入前驱节点，存入被引用对象e，返回新节点位置 |
insertAsSucc() |
插入后继节点，存入被引用对象e，返回新节点位置 |
ListNode模板类
按照上表所定义的ADT接口，可定义列表节点模板类如下。出于简洁与效率的考虑，这里并未对ListNode对象做封装处理。列表节点数据项的类型，通过模板参数T指定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17listNode.h
代码3.1 列表节点模板类
typedef int Rank; // 秩
template <typename T> struct ListNode { // 列表节点模板类(以双向链表形式实现)
// 成员
T data; ListNodePosi(T) pred; ListNodePosi(T) succ; // 数值、前驱、后继
// 构造函数
ListNode(){} // 针对header和trailer的构造
ListNode(T e, ListNodePosi(T) p = NULL, ListNodePosi(T) s = NULL)
: data(e), pred (p), succ(s) {} // 默认构造器
// 操作接口
ListNodePosi(T) insertAsPred(T const& e); // 紧靠当前节点之前插入新节点
ListNodePosi(T) insertAsSucc(T const& e); // 紧靠当前节点之后插入新节点
};
每个节点都存有数据对象data。还设有指针pred和succ，分别指向其前驱和后继，默认取作NULL。
3.2.2 列表
ADT接口
作为一种抽象数据类型，列表对象应支持以下操作接口。
| 操作接口 | 功能 | 适用对象 |
|---|---|---|
size() |
报告列表当前的规模(节点总数) | 列表 |
first() last() |
返回值、末节点的位置 | 列表 |
insertAsFirst(e) insertAsLast(e) |
将e当作首、末节点插入 | 列表 |
insertA(p, e) insertB(p, e) |
将e当作节点p的直接后继、前驱插入 | 列表 |
remove(p) |
删除位置p处的节点，返回其数值 | 列表 |
disordered() |
判断所有节点是否已按非降序排列 | 列表 |
sort() |
调整各节点的位置，使之按非降序排列 | 列表 |
find(e) |
查找目标元素e，失败时返回NULL | 列表 |
search(e) |
查找目标元素e，返回不大于e且秩最大的节点 | 有序列表 |
deduplicate() |
剔除重复节点 | 列表 |
uniquify() |
剔除重复节点 | 有序列表 |
traverse() |
遍历并统一处理所有节点，处理方法由函数对象指定 | 列表 |
注意用以指示插入和删除操作位置的结点p。这里约定它或者在此前经查找已经确定，或者从此前的其它操作返回或沿用。这些也是列表类结构的典型操作方式。
与向量一样，有序列表的唯一化，比无序列表效率更高。然而由于只能通过位置指针以局部移动的方式访问节点，尽管有序列表中节点在逻辑上时钟按照大小次序排列，其查找操作的效率并没实质改进。
List模板类
根据上表定义的ADT接口，可定义List模板类如下。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64list.h
代码3.2 列表模板类
template <typename T> class List { // 列表模板类
private:
int _size; ListNodePosi(T) header; ListNodePosi(T) trailer; // 规模、头哨兵、尾哨兵
protected:
void init(); // 列表创建时的初始化
int clear(); // 清除所有节点
void copyNodes(ListNodePosi(T), int); // 复制列表中自位置p起的n项
void merge ( ListNodePosi(T)&, int, List<T>&, ListNodePosi(T), int); // 归并
void mergeSort(ListNodePosi(T)&, int); // 对从p开始连续的n个节点归并排序
void selectionSort(ListNodePosi(T), int); // 对从p开始连续的n个节点选择排序
void insertionSort(ListNodePosi(T), int); // 对从p开始连续的n个节点插入排序
public:
// 构造函数
List(){ init(); } // 默认
List(List<T> const& L); // 整体复制列表L
List(List<T> const& L, Rank r, int n); // 复制列表L中自第r项起的n项
List(ListNodePosi(T) p, int n); // 复制列表中自位置p起的n项
// 析构函数
~List(); // 释放(包含头、尾哨兵在内的)所有节点
// 只读访问接口
Rank size() const { return _size; } // 规模
bool empty() const { return _size <= 0; } // 判空
T& operator[](Rank r) const; // 重载，支持循秩访问(效率低)
ListNodePosi(T) first() const { return header->succ; } // 首节点位置
ListNodePosi(T) last() const { return trailer->pred; } // 末节点位置
bool valid(ListNodePosi(T) p) // 判断位置p是否对外合法
{ return p && (trailer != p) && (header != p); } // 将头、尾节点等同于NULL
int disordered() const; // 判断列表是否已排序
ListNodePosi(T) find(T const& e) const // 无序列表查找
{ return find(e, _size, trailer); }
ListNodePosi(T) find(T const& e, int n, ListNodePosi(T) p) const; // 无序区间查找
ListNodePosi(T) search(T const& e) const // 有序列表查找
{ return search(e, _size, trailer); }
ListNodePosi(T) search(T const& e, int n, ListNodePosi(T) p) const; // 有序区间查找
ListNodePosi(T) selectMax(ListNodePosi(T) p, int n); // 在p及其n-1个后继中选出最大者
ListNodePosi(T) selectMax(){ return selectMax(header->succ, _size); } // 整体最大者
// 可写访问接口
ListNodePosi(T) insertAsFirst(T const& e); // 将e当作首节点插入
ListNodePosi(T) insertAsLast(T const& e); // 将e当作末节点插入
ListNodePosi(T) insertA(ListNodePosi(T) p, T const& e); // 将e当作p的后继插入
ListNodePosi(T) insertB(ListNodePosi(T) p, T const& e); // 将e当作p的前驱插入
T remove(ListNodePosi(T) p); // 删除合法位置p处的节点，返回被删除节点
void merge(List<T>& L){ merge(first(), size, L, L.first(), L._size); } // 全列表归并
void sort(ListNodePosi(T) p, int n); // 列表区间排序
void sort(){ sort(first(), _size); } // 列表整体排序
int deduplicate(); // 无序去重
int uniquify(); // 有序去重
void reverse(); // 前后倒置(习题)
// 遍历
void traverse(void(*) (T&)); // 遍历，依次实施visit操作(函数指针，只读或局部性修改)
template <typename VST> // 操作器
void traverse(VST&); // 遍历，依次实施visit操作(函数对象，可全局性修改)
}; // List
由上述代码可见，列表结构的实现方式与第二章的向量结构颇为相似：通过模板参数T指定列表元素的类型；在内部设置私有变量以记录当前规模等状态信息；基于多种排序算法提供统一的sort()接口，以将列表转化为有序列表。
等效地，头、首、末、尾节点的秩可分别理解为-1、0、n-1、n。头节点和尾节点是与生俱来的，而且二者并不相同first和last并不见得不相同，甚至不能保证他们存在，对外first、last可见，header和trailer不可见。
3.3 列表
3.3.1 头、尾节点
List对象中私有的头节点(header)和尾节点(trailer)始终存在，但对外并不可见。对外部可见的数据节点如果存在，则其中的第一个和最后一个分别称作首节点(first node)和末节点(last node)。
就内部结构而言，头节点紧邻于首节点之前，尾节点紧邻于末节点之后。这类经封装之后从外部不可见的节点，称作哨兵节点(sentinel node)。由于哨兵节点对外并不可见，因此两个哨兵节点从外部被等效地视作NULL。
设置哨兵节点之后，对于从外部可见的任一节点而言，其前驱和后继在列表内部都必然存在，故可简化算法的描述与实现。此外更重要地，哨兵节点的引入，也使得相关算法不必再对各种便捷退化情况做专门的处理，从而避免出错的可能。
尽管哨兵节点也需占用一定的空间，但只不过是常数规模，其成本远远低于由此带来的便利。
3.3.2 默认构造方法
创建List对象时，默认构造方法调用统一初始化过程init()，在列表内部创建一对头、尾哨兵节点，并适当地设置其前驱、后继指针构成一个双向链表。1
2
3
4
5
6
7
8
9
10list_initialize.h
代码3.3 列表类内部方法init()
template <typename T> void List<T>::init() { // 列表初始化，在创建列表对象时统一调用
header = new ListNode<T>; // 创建头哨兵节点
trailer = new ListNode<T>; // 创建尾哨兵节点
header->succ = trailer; header->pred = NULL;
trailer->pred = header; trailer->succ = NULL;
_size = 0; // 记录规模
}
该链表对外的有效部分初始化为空，哨兵节点对外不可见，此后引入的新节点都将陆续插入于这对哨兵节点之间。
该过程仅涉及常数次基本操作，共需运行常数时间。
3.3.3 由秩到位置的转换
通过重载操作符”[]”来实现通过秩来指定列表节点，提供一个转换接口。1
2
3
4
5
6
7
8
9list_bracket.h
代码3.4 重载列表类的下标操作符
template <typename T> // 重载下标操作符，以通过秩直接访问列表节点(虽方便，效率低，需慎用)
T& List<T>::operator[](Rank r) const { // assert: 0 <= r < size
ListNodePosi(T) p = first(); // 从首节点出发
while (0 < r--) p = p -> succ; // 顺数第r个节点即是
return p -> data; // 目标节点，返回其中所存元素
} // 从任一节点的秩，亦即其前驱的总数
从首节点出发，顺着后继指针前进r步。其中每步迭代仅需常数时间，故该算法的总体运行时间应为$O(r + 1)$，线性正比于目标节点的秩。
相比于向量同类接口的$O(1)$复杂度，列表的这一效率十分低下——根源在于，列表的存储和访问方式不同。虽然当r大于n/2时，从trailer出发沿pred指针逆行查找，可以在一定程度上减少迭代次数，但就总体的平均效率而言，这一改进并无实质意义。
3.3.4 查找
实现
代码3.2中列表ADT针对整体和区间查找，重载了操作接口find(e)和find(e, p, n)。其中，前者作为特例，可以直接调用后者。因此只需实现后一接口1
2
3
4
5
6
7
8
9list_find.h
代码3.5 无序列表元素查找接口find()
template <typename T> // 在无序列表内节点p(trailer)的n个(真)前驱中，找到等于e的最后者
ListNodePosi(T) List<T>::find(T const& e, int n, ListNodePosi(T) p) const { // O(n)
while (0 < n--) // (0 <= n <= rank(p) < _size)对于p的最近的n个前驱，从右向左
if (e == (p = p -> pred) -> data) return p; // 逐个比对，直至命中或范围越界(这里假定类型T已重载操作符"==")
return NULL; // p越出左边界意味着区间内不含e，查找失败
} // 失败时，返回NULL
复杂度
以上算法的思路及过程与无序向量的顺序查找算法Vector::find()(代码2.10)相仿，故时间复杂度也应是$O(n)$，线性正比于查找区间的宽度。
3.3.5 插入
接口
1 | list_insert.h |
这些接口的实现都可转化为列表节点对象的前插入或后插入接口。
前插入
将新元素e作为当前节点的前驱插至列表。
1
2
3
4
5
6
7
8
9listnode_insertAsPred()算法
代码3.7 ListNode::insertAsPred()算法
template <typename T> // 将e紧靠当前节点之前插入于当前节点所属列表(设有哨兵头节点header)
ListNodePosi(T) ListNode<T>::insertAsPred(const T &e) {
ListNodePosi(T) x = new ListNode(e, pred, this); // 创建新节点
pred -> succ = x; pred = x; // 设置正向链接(次序不可颠倒)
return x; // 返回新节点的位置
} // 得益于哨兵，即便this为首节点亦不必特殊处理——此时等效于insertAsFirst(e)
该算法首先创建新节点new，构造函数同时将其数据项置为e，并令其后继链接succ指向当前节点，令其前驱链接pred指向当前节点的前驱节点。随后使new成为当前节点前驱节点的后继，使new成为当前节点的前驱(次序不能颠倒)。最终，经过如此调整，新节点即被顺利地插至列表的这一局部。
得益于头哨兵节点的存在，即便当前节点为列表的首节点，其前驱也必然存在，故不必另做特殊处理。
后插入
将新元素e作为当前节点的后继插至列表的过程。1
2
3
4
5
6
7
8
9listnode_insertassucc.h
代码3.8 ListNode::insertAsSucc()算法
template <typename T> // 将e紧随当前节点之后插入于当前节点所属列表(设有哨兵尾节点trailer)
ListNodePosi(T) ListNode<T>::insertAsSucc(const T &e) {
ListNodePosi(T) x = new ListNode(e, this, succ); // 创建新节点
succ -> pred = x; succ = x; // 设置逆向链接
return x; // 返回新节点的位置
}
后插入的操作过程以及最终效果与前插入完全对称。
复杂度
上述两种插入操作过程，仅涉及局部的两个原有节点和一个新节点，且不含任何迭代或递归。若假设当前节点已经定位，不计入此前的查找所消耗的时间，则它们都可在常数时间内完成。
3.3.6 基于复制的构造
copyNodes()
List模板类中提供的多种形式的对原列表的整体或列表的构造函数都可概括和转化为底层内部方法copyNodes()。1
2
3
4
5
6
7
8list_copynodes.h
代码3.9 列表类内部方法copyNodes()
template <typename T> // 列表类内部方法:复制列表中自位置p起的n项
void List<T>::copyNodes(ListNodePosi(T) p, int n) { // p合法，且至少有n-1个真后继节点
init(); // 创建头，尾哨兵节点并做初始化
while (n--){ insertAsLast(p -> data); p = p -> succ; } // 将起始自p的n项依次作为末节点插入
}
在输入参数合法的前提下，copyNodes()首先调用init()方法，创建头、尾哨兵节点并做相应的初始化处理，然后自p所指节点起，从原列表中取出n个相邻的节点，并逐一作为末节点插至新列表中。
init()操作以及各步迭代中的插入操作均只需常数时间，故copyNodes()过程总体的运行时间应为$O(n + 1)$，线性正比于待复制列表区间的长度n。
基于复制的构造
基于上述copyNodes()方法可以实现多种接口，通过复制已有列表的区间或整体，构造出新列表。1
2
3
4
5
6
7
8
9
10
11list_constructor_by_copying.h
代码3.10 基于复制的列表构造方法
template <typename T> // 复制列表中自位置p起的n项(assert: p为合法位置，且至少有n-1个后继节点)
List<T>::List(ListNodePosi(T) p, int n){ copyNodes(p, n); }
template <typename T> // 整体复制列表L
List<T>::List(List<T> const& L){ copyNodes(L.first(), L._size); }
template <typename T> // 复制L中自第r项起的n项(assert: r+n <= L._size)
List<T>::List(List<T> const& L, int r, int n){ copyNodes(L[r], n); }
其中为了复制列表L中自秩r起的n个相邻节点，List(L, r, n)需借助重载后的下标操作符，找到待复制区间起始节点的位置，然后再以此节点作为参数调用copyNodes()。根据由秩到位置的转换这节分析出的结论，需要花费$O(r + 1)$的时间才能将r转换为起始节点的位置，故该复制接口的总体复杂度应为$O(r + n + 1)$，线性正比于被复制节点的最高秩。由此也可再次看出，在诸如列表之类采用动态存储策略的结构中，循秩访问远非有效的方式。
3.3.7 删除
实现
在列表中删除指定节点p的算法。1
2
3
4
5
6
7
8
9list_remove.h
代码3.11 列表节点删除接口remove()
template <typename T> T List<T>::remove(ListNodePosi(T) p){ // 合法删除节点p，返回其数值
T e = p -> data; // 备份待删除节点的数值(假定T类型可直接赋值)
p -> pred -> succ = p -> succ; p -> succ -> pred = p -> pred; // 后继、前驱
delete p; _size++; // 释放节点，更新规模
return e; // 返回备份的数值
}
为了删除位置p处的节点，令其前驱节点与后继节点相互链接。然后释放掉已经孤立出来的节点p，同时相应地更新列表规模计数器_size()。最终经过如此调整后之后，原节点p即被顺利地从列表中摘除。
在这里也能体会到哨兵节点的作用，即便p所指的是列表中唯一对外的节点(其前驱和后继都是哨兵节点)，remove()算法依然可以正常运转。
复杂度
以上过程仅涉及常数次基本操作，故若不计入此前为查找并确定位置p所消耗的时间，列表的节点删除操作可在常数时间内完成。
3.3.8 析构
释放资源及清除节点
1 | list_destructor.h |
列表的析构需要首先调用clear()接口删除并释放所有对外部有效的节点，然后释放内部的头、尾哨兵节点。1
2
3
4
5
6
7
8list_clear.h
代码3.13 列表清空方法clear()
template <typename T> int List<T>::clear() { // 清空列表
int oldSize = _size;
while (0 < _size) remove(header -> succ); // 反复删除首节点，直至列表变空
return oldSize;
}
复杂度
这里的时间消耗主要来自clear()操作，该操作通过remove()接口反复删除列表的首节点。因此，clear()方法以及整个析构方法的运行时间应为$O(n)$，线性正比于列表原先的规模。
3.3.9 唯一化
实现
剔除无序列表中重复元素的接口dedupulicate()。1
2
3
4
5
6
7
8
9
10
11
12
13list_deduplicate.h
代码3.14 无序列表剔除重复节点接口dedupulicate()
template <typename T> int List<T>::deduplicate() { // 剔除无序列表中的重复节点
if (_size < 2) return 0; // 平凡列表自然无重复
int oldSize = _size; // 记录原规模
ListNodePosi(T) p = header; Rank r = 0; // p从首节点开始
while (trailer != (p = p -> succ)){ // 依次直到末节点
ListNodePosi(T) q = find(p -> data, r, p); // 在p的r个(真)前驱中查找雷同者(r为整个前缀的长度)
q ? remove(q) : r++; // 若的确存在，则删除之；否则秩加一
} // assert: 循环过程中的任意时刻，p的所有前驱互不相同
return oldSize - _size; // 列表规模变化量，即被删除元素总数
}
与算法Vector::deduplicate()类似，这里也是自前向后一次处理各节点p，一旦通过find()接口在p的前驱中查到雷同者，则随即调用remove()接口将其删除。
上述代码while循环中能否remove(p)而不是remove(q)?
不可以，因为下次迭代中p = p->succ操作存在风险，这时p已经没有明确指向很有可能发生错误。
正确性
向量与列表中元素的逻辑次序一致，故二者的deduplicate()算法亦具有类似的不变性和单调性，故正确性均可保证。
复杂度
与无序向量的去重算法一样，该算法总共需要做$O(n)$步迭代。每一步迭代中find()操作所需的时间线性正比于查找区间宽度，即当前节点的秩；列表节点每次remove()操作仅需常数时间。因此，总体执行时间应为:
$1 + 2 + 3 + … + n = n \cdot (n + 1) /2 = O(n^2) $
相对于无序向量，尽管此处节点删除操作所需的时间减少，但总体渐进复杂度并无改进。
3.3.10 遍历
1 | list_traverse.h |
该接口的设计思路与实现方式，与向量的对应接口如出一辙，复杂度也相同。
3.4 有序列表
若列表中所有节点的逻辑次序与其大小次序完全一致，则称作有序列表(sorted list)。
3.4.1 唯一化
与有序向量同理，有序列表中的雷同节点也必然(在逻辑上)彼此紧邻。1
2
3
4
5
6
7
8
9
10
11
12list_uniquify.h
代码3.16 有序列表剔除重复节点接口uniquify()
template <typename T> int List<T>::uniquify() { // 成批剔除重复元素，效率更高
if (_size < 2) return 0; // 平凡列表自然无重复
int oldSize = _size; // 记录原规模
ListNodePosi(T) p = first(); ListNodePosi(T) q; // p为各区段起点，q为其后继
while (trailer != (q = p -> succ)) // 反复考察紧邻的节点对(p, q)
if (p -> data != q -> data) p = q; // 若互异，则转向下一区段
else remove(q); // 否则(雷同)，则删除后者
return oldSize - _size; // 列表规模变化量，即被删除元素总数
}
算法概括：位置指针p和q分别指向每一对相邻的节点，若二者雷同则删除q，否则转向下一对相邻节点。如此反复迭代，直至检查过所有节点。
时间复杂度：整个过程的运行时间为$O(_size) = O(n)$，线性正比于列表原先的规模。
3.4.2 查找
实现
1 | list_search.h |
顺序查找
与有序向量的各种查找算法相比，该算法完全不同；反过来，除了循环终止条件的细微差异，多数部分反倒与无序列表的顺序查找算法几乎一样。
原因在于，尽管有序列表中的节点已在逻辑上按次序单调排列，但在动态存储策略中，节点的物理地址与逻辑次序毫无关系，故无法像有序向量那样自如地采用减治策略，从而不得不继续沿用无序列表的顺序查找策略。
复杂度
与无序向量的查找算法同理:最好情况下的运行时间为$O(1)$，最坏情况下为$O(n)$。在等概率的前提下，平均运行时间也是$O(n)$，线性正比于查找区间的宽度。
3.5 排序器
3.5.1 统一入口
1 | list_sort.h |
3.5.2 插入排序
构思
插入排序(insertionsort)算法适用于包括向量与列表在内的任何序列结构。
算法的思路可简要描述为：始终将整个序列视作并切分为两部分：有序的前缀，无序的后缀；通过迭代，反复地将后缀的首元素转移至前缀中。由此亦可看出插入排序算法的不变性：
在任何时刻，相对于当前节点$e = S[r]$，前缀$S[0, r)$总是业已有序
算法开始时该前缀为空，不变性自然满足。
实现
有序列表的节点查找算法。1
2
3
4
5
6
7
8
9
10list_insertionsort.h
代码3.19 列表的插入排序
template <typename T> // 列表的插入排序算法：对起始于位置p的n个元素排序
void List<T>::insertionSort(ListNodePosi(T) p, int n){ // valid(p) && rank(p) + n <= size
for (int r = 0; r < n; r++){ // 逐一为各节点
insertA(search(p->data, r, p), p->data); // 查找适当的位置并插入
}
p = p -> succ; remove(p -> pred); // 转向下一节点
}
有多个元素命中时search()接口将返回其中最靠后者，排序之后重复元素将保持其原有次序，故以上插入排序算法属于稳定算法。
复杂度
插入排序算法共由n步迭代组成，故其运行时间应取决于，各步迭代中所执行的查找、删除及插入操作的效率。插入操作insertA()和删除操作remove()均只需$O(1)$时间；查找操作search()所需时间可在$O(1)$至$O(n)$之间浮动。
当输入序列已经有序时，该算法中的每次search()操作均仅需$O(1)$时间，总体运行时间为$O(n)$。但反过来，若输出序列完全逆序，则各次search()操作所需时间将现行递增，累计共需$O(n^2)$时间。在等概率条件下，平均仍需要$O(n^2)$时间。
3.5.3 选择排序
选择排序(selectionsort)也适用于向量与列表之类的序列结构。
构思
与插入排序类似，该算法也将序列划分为无序前缀和有序后缀两部分；此外，还要求前缀不大于后缀。如此，每次只需从前缀中选出最大者，并作为最小元素转移至后缀中，即可使有序部分的范围不断扩张。
同样地，上述描述也给出了选择排序算法过程所具有的不变性：
在任何时刻，后缀$S(r, n)$已经有序，且不小于前缀$S[0, r]$
在算法的初始时刻，后缀为空，不变性自然满足。假设不变性已满足，调用无序序列的查找算法，从前缀中找出最大者M。然后将M从前缀中取出并作首元素插入后缀，即可使得后缀的范围扩大，并继续保持有序。
如此，该后缀的范围可不断扩展。当其最终覆盖整个序列时，亦即整体有序。
实现
1 | list_selectionsort |
其中的selectMax()接口用于在无序列表中定位最大的节点。selectMax()算法也称作画家算法。1
2
3
4
5
6
7
8
9
10
11list_selectmax.h
代码3.21 列表最大节点的定位
template <typename T> // 从起始于位置p的n个元素中选出最大者
ListNodePosi(T) List<T>::selectMax(ListNodePosi(T) p, int n){
ListNodePosi(T) max = p; // 最大者暂定为首节点p
for(ListNodePosi(T) cur = p; 1 < n; n--) // 从首节点p出发，将后续节点逐一与max比较
if (!lt((cur = cur -> succ) -> data, max -> data)) // 若当前元素不小于max，则
max = cur; // 更新最大元素位置记录
return max; // 返回最大节点位置
}
复杂度
与插入排序类似地，选择排序亦由n步迭代组成，故其运行时间取决于各步迭代中查找及插入操作的效率。根据之前的结论，insertB()和remove()均只需$O(1)$时间。selectMax()每次必须遍历整个无序前缀，耗时应线性正比于前缀长度；全程累计耗时$O(n^2)$。
无论输入序列中各元素的大小次序如何，以上n次selectMax()调用的累计耗时总是$\Theta (n^2)$。也就是说，其最好和最坏情况下的渐进效率相同。
选择排序属于CBA式算法，故相对之前给出的$\Omega(nlogn)$下界，$\Theta(n^2)$的效率应有很大的改进空间。借助更为高级的数据结构，可以令单次selectMax()操作的复杂度降至$O(logn)$，从而使选择排序的整体效率提高至$O(nlogn)$（insert()和remove()操作需要动态空间分配，虽然可以认为是依然是常数的时间复杂度，但从实际的时间消耗而言，它大致是通常基本操作的100倍，因为这对操作应该尽可能少的使用）。
3.5.4 归并排序
基于二路归并的向量排序算法，其构思也同样适用于列表结构。有序列表的二路归并不仅可以实现，而且能够达到与有序向量二路归并同样高的效率。
二路归并算法的实现
1 | list_merge.h |
List::merge()可以将另一有序列表L中起始于节点q、长度为m的子列表，与当前有序列表中起始于节点p、长度为n的子列表做二路归并。
归并时间
二路归并算法merge()的时间成本主要消耗于其中的迭代。该迭代反复地比较两个子列表的首节点p和q，并视其大小相应地令p指向其后继，或将节点q取出并作为p的前驱插入前一子列表。当且仅当后一子列表中所有节点均处理完毕时，迭代才会终止。因此，在最好情况下，共需迭代m次；而在最坏情况下，则共需迭代n次。
总体而言，共需$O(m+n)$时间，线性正比于两个子列表的长度之和。
分治策略
采用分治策略并基于以上有序列表的二路归并算法，递归地描述和实现列表的归并排序算法。1
2
3
4
5
6
7
8
9
10
11
12
13
14list_mergesort.h
代码3.23 列表的归并排序
template <typename T> // 列表的归并排序算法：对起始于位置p的n个元素排序
void List<T>::mergeSort(ListNodePosi(T) & p, int n){ // valid(p) && rank(p) + n <= size
if (n < 2) return; // 若待排序范围已足够小，则直接返回；否则...
int m = n >> 1; // 以重点为界
ListNodePosi(T) q = p;
for (int i = 0; i < m; i++) {
q = q -> succ; // 均分列表
}
mergeSort(p, m); mergeSort(q, n - m); // 对前、后子列表分别排序
merge(p, m, *this, q, n - m); // 归并
} // 注意：排序后，p依然指向归并后区间的(新)起点
排序时间
根据该算法的流程，为对长度为n的列表做归并排序，首先需要花费线性时间确定居中的切分节点，然后递归地对长度均为n/2的两个子列表做归并排序，最后还需花费线性的时间做二路归并。因此，仿照对向量归并排序算法的分析方法，同样可知其复杂度应为$O(nlogn)$。
注意，在子序列的划分阶段，向量与列表归并排序算法之间存在细微但本质的区别。前者支持循秩访问的方式，故可在$O(1)$时间内确定切分中点；后者仅支持循位置访问的方式，故需花费$O(n)$时间。但在有序子序列的合并阶段二者均需$O(n)$时间，故二者的渐进时间复杂度依然相等。
最后，尽管二路归并算法并未对子列表的长度做出任何限制，但这里出于整体效率的考虑，在划分子列表时宁可花费$O(n)$时间使得二者尽可能接近等长。反之，若为省略这部分时间而不保证划分的均衡性，则反而可能导致整体效率的下降。(习题[3-16])